// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为 target 的四元组。

// 思路：双指针，和三数之和思路一样，只不过多了一重循环
// 时间复杂度：O(n^3)
// 空间复杂度：O(1)

function fourSum(arr, target) {
    arr.sort((a, b) => a - b)
    const ans = []
    for (let i = 0; i < arr.length - 3; i++) {
        if (i > 0 && arr[i] === arr[i - 1]) {
            continue
        }
        for (let j = i + 1; j < arr.length - 2; j++) {
            // 这里注意要大于i+1
            if (j > i + 1 && arr[j] === arr[j - 1]) {
                continue
            }
            let left = j + 1
            let right = arr.length - 1
            while (left < right) {
                let sum = arr[i] + arr[j] + arr[left] + arr[right]
                if (sum === target) {
                    ans.push([arr[i], arr[j], arr[left], arr[right]])
                    // 需要判断是否有相同的数，防止结果重复
                    while (left < right && arr[right] === arr[right - 1]) {
                        right--
                    }
                    while (left < right && arr[left] === arr[left + 1]) {
                        left++
                    }
                    left++
                    right--
                } else if (sum > target) {
                    right--
                } else {
                    left++
                }
            } 
        }        
    }
    return ans
}

let nums = [1,0,-1,0,-2,2]
nums = [2,2,2,2,2]
console.log(fourSum(nums, 8))